#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <vector>

using namespace std;
using LL = long long;

const int N = 1e5 + 10;

int n;
vector<int> nums;
int q[N];
struct Node{
    int l, r;
    int sum;
}node[N * 4];

int find(int x){
    return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}

void pushdown(int u){
    node[u].sum = node[u << 1].sum + node[u << 1 | 1].sum;
}

void build(int u, int l, int r){
    node[u].l = l, node[u].r = r;
    if(l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}


void modify(int u, int x){
    if(node[u].l == x && node[u].r == x){
        node[u].sum ++;
    }else{
        int mid = (node[u].l + node[u].r) >> 1;
        if(x <= mid) modify(u << 1, x);
        if(x > mid) modify(u << 1 | 1, x);
        pushdown(u);
    }
}

int getk(int u, int k){
    if(node[u].l == node[u].r){
        return nums[node[u].l];
    }else{
        if(node[u << 1].sum < k){
            return getk(u << 1 | 1, k - node[u << 1].sum);
        }else{
            return getk(u << 1, k);
        }
    }

    
}

int main(){
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);

    scanf("%d", &n);
    for(int i = 1; i <= n; i ++){
        scanf("%d", &q[i]);
        nums.push_back(q[i]);
    }
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());

    int sz = nums.size() - 1;
    build(1, 0, sz);


    for(int i = 1; i <= n; i ++){
        modify(1, find(q[i]));
        if(i % 2){
            printf("%d\n", getk(1, (i + 1) / 2));
        }
    }

    return 0;
}